/* Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.flowable.bpmn;

import com.mxgraph.layout.mxGraphLayout;
import com.mxgraph.model.mxCell;
import com.mxgraph.model.mxGeometry;
import com.mxgraph.model.mxIGraphModel;
import com.mxgraph.util.mxRectangle;
import com.mxgraph.view.mxGraph;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * BPMNLayout
 * 
 * @author Shi Yaoqiang(shi_yaoqiang@yahoo.com)
 */
public class BPMNLayout extends mxGraphLayout {

    // NEW

    protected BpmnAutoLayout bpmnAutoLayout;

    public void setBpmnAutoLayout(BpmnAutoLayout bpmnAutoLayout) {
        this.bpmnAutoLayout = bpmnAutoLayout;
    }

    // NEW

    /**
     * Specifies the orientation of the layout. Default is true.
     */
    protected boolean horizontal;

    /**
     * Specifies if edge directions should be inverted. Default is false.
     */
    protected boolean invert;

    /**
     * If the parent should be resized to match the width/height of the tree. Default is true.
     */
    protected boolean resizeParent = true;

    /**
     * Specifies if the tree should be moved to the top, left corner if it is inside a top-level layer. Default is true.
     */
    protected boolean moveTree = true;

    /**
     * Specifies if all edge points of traversed edges should be removed. Default is true.
     */
    protected boolean resetEdges = true;

    /**
     * Holds the levelDistance. Default is 40.
     */
    protected int levelDistance = 40;

    /**
     * Holds the nodeDistance. Default is 20.
     */
    protected int nodeDistance = 20;

    /**
     * 
     * @param graph
     */
    public BPMNLayout(mxGraph graph) {
        this(graph, true);
    }

    /**
     * 
     * @param graph
     * @param horizontal
     */
    public BPMNLayout(mxGraph graph, boolean horizontal) {
        this(graph, horizontal, false);
    }

    /**
     * 
     * @param graph
     * @param horizontal
     * @param invert
     */
    public BPMNLayout(mxGraph graph, boolean horizontal, boolean invert) {
        super(graph);
        setUseBoundingBox(false);
        this.horizontal = horizontal;
        this.invert = invert;
    }

    @Override
    public mxGraph getGraph() {
        return graph;
    }

    /**
     * Returns a boolean indicating if the given mxCell should be ignored as a vertex. This returns true if the cell has no connections.
     * 
     * @param vertex
     *            Object that represents the vertex to be tested.
     * @return Returns true if the vertex should be ignored.
     */
    @Override
    public boolean isVertexIgnored(Object vertex) {
        return super.isVertexIgnored(vertex) || graph.isSwimlane(vertex) || graph.getModel().getGeometry(vertex).isRelative() || graph.getConnections(vertex).length == 0;
    }

    /**
     * @return the horizontal
     */
    public boolean isHorizontal() {
        return horizontal;
    }

    /**
     * @param horizontal
     *            the horizontal to set
     */
    public void setHorizontal(boolean horizontal) {
        this.horizontal = horizontal;
    }

    /**
     * @return the invert
     */
    public boolean isInvert() {
        return invert;
    }

    /**
     * @param invert
     *            the invert to set
     */
    public void setInvert(boolean invert) {
        this.invert = invert;
    }

    /**
     * @return the resizeParent
     */
    public boolean isResizeParent() {
        return resizeParent;
    }

    /**
     * @param resizeParent
     *            the resizeParent to set
     */
    public void setResizeParent(boolean resizeParent) {
        this.resizeParent = resizeParent;
    }

    /**
     * @return the moveTree
     */
    public boolean isMoveTree() {
        return moveTree;
    }

    /**
     * @param moveTree
     *            the moveTree to set
     */
    public void setMoveTree(boolean moveTree) {
        this.moveTree = moveTree;
    }

    /**
     * @return the resetEdges
     */
    public boolean isResetEdges() {
        return resetEdges;
    }

    /**
     * @param resetEdges
     *            the resetEdges to set
     */
    public void setResetEdges(boolean resetEdges) {
        this.resetEdges = resetEdges;
    }

    /**
     * @return the levelDistance
     */
    public int getLevelDistance() {
        return levelDistance;
    }

    /**
     * @param levelDistance
     *            the levelDistance to set
     */
    public void setLevelDistance(int levelDistance) {
        this.levelDistance = levelDistance;
    }

    /**
     * @return the nodeDistance
     */
    public int getNodeDistance() {
        return nodeDistance;
    }

    /**
     * @param nodeDistance
     *            the nodeDistance to set
     */
    public void setNodeDistance(int nodeDistance) {
        this.nodeDistance = nodeDistance;
    }

    @Override
    public void execute(Object parent) {
        mxIGraphModel model = graph.getModel();
        List<Object> roots = graph.findTreeRoots(parent, true, invert);
        // if (getGraph().isOrganizationElement(parent)) {
        // roots = Arrays.asList(graph.getSelectionCells());
        // }
        for (Object root : roots) {
            parent = model.getParent(root);

            if (isBoundaryEvent(root)) {
                parent = model.getParent(parent);
            }
            model.beginUpdate();

            try {
                TreeNode node = dfs(root, parent, null);

                if (node != null) {
                    layout(node);

                    double x0 = graph.getGridSize();
                    double y0 = x0;

                    if (!moveTree || parent == graph.getDefaultParent() || parent == graph.getCurrentRoot()) {
                        mxGeometry g = model.getGeometry(root);
                        if (g.isRelative()) {
                            g = model.getGeometry(model.getParent(root));
                        }
                        if (g != null) {
                            x0 = g.getX();
                            y0 = g.getY();
                        }
                    }

                    mxRectangle bounds = null;

                    if (horizontal) {
                        bounds = horizontalLayout(node, x0, y0, null);
                    } else {
                        bounds = verticalLayout(node, null, x0, y0, null);
                    }

                    if (bounds != null) {
                        double dx = 0;
                        double dy = 0;

                        if (bounds.getX() < 0) {
                            dx = Math.abs(x0 - bounds.getX());
                        }

                        if (bounds.getY() < 0) {
                            dy = Math.abs(y0 - bounds.getY());
                        }

                        if (parent != null) {
                            mxRectangle size = graph.getStartSize(parent);
                            dx += size.getWidth();
                            dy += size.getHeight();

                            // Resize parent swimlane
                            if (resizeParent && !graph.isCellCollapsed(parent)) {
                                mxGeometry g = model.getGeometry(parent);

                                if (g != null) {
                                    double width = bounds.getWidth() + size.getWidth() - bounds.getX() + 2 * x0;
                                    double height = bounds.getHeight() + size.getHeight() - bounds.getY() + 2 * y0;

                                    g = (mxGeometry) g.clone();

                                    if (g.getWidth() > width) {
                                        dx += (g.getWidth() - width) / 2;
                                    } else {
                                        g.setWidth(width);
                                    }

                                    if (g.getHeight() > height) {
                                        if (horizontal) {
                                            dy += (g.getHeight() - height) / 2;
                                        }
                                    } else {
                                        g.setHeight(height);
                                    }

                                    model.setGeometry(parent, g);
                                }
                            }
                        }
                        if (model.getParent(node.cell) != graph.getCurrentRoot() && model.getParent(node.cell) != graph.getDefaultParent()) {
                            moveNode(node, dx, dy);
                        }
                    }
                }
            } finally {
                model.endUpdate();
            }
        }
    }

    protected boolean isBoundaryEvent(Object obj) {
        if (obj instanceof mxCell) {
            mxCell cell = (mxCell) obj;
            return cell.getId().startsWith("boundary-event-");
        }
        return false;
    }

    /**
     * Moves the specified node and all of its children by the given amount.
     */
    protected void moveNode(TreeNode node, double dx, double dy) {
        node.x += dx;
        node.y += dy;
        apply(node, null);

        TreeNode child = node.child;

        while (child != null) {
            moveNode(child, dx, dy);
            child = child.next;
        }
    }

    /**
     * Does a depth first search starting at the specified cell. Makes sure the specified swimlane is never left by the algorithm.
     */
    protected TreeNode dfs(Object cell, Object parent, Set<Object> visited) {
        if (visited == null) {
            visited = new HashSet<>();
        }

        TreeNode node = null;

        mxIGraphModel model = graph.getModel();
        if (cell != null && !visited.contains(cell) && (!isVertexIgnored(cell) || isBoundaryEvent(cell))) {
            visited.add(cell);
            node = createNode(cell);

            TreeNode prev = null;
            Object[] out = graph.getEdges(cell, parent, invert, !invert, false);

            for (int i = 0; i < out.length; i++) {
                Object edge = out[i];

                if (!isEdgeIgnored(edge)) {
                    // Resets the points on the traversed edge
                    if (resetEdges) {
                        setEdgePoints(edge, null);
                    }

                    // Checks if terminal in same swimlane
                    Object target = graph.getView().getVisibleTerminal(edge, invert);
                    TreeNode tmp = dfs(target, parent, visited);

                    if (tmp != null && model.getGeometry(target) != null) {
                        if (prev == null) {
                            node.child = tmp;
                        } else {
                            prev.next = tmp;
                        }

                        prev = tmp;
                    }
                }
            }
        }

        return node;
    }

    /**
     * Starts the actual compact tree layout algorithm at the given node.
     */
    protected void layout(TreeNode node) {
        if (node != null) {
            TreeNode child = node.child;

            while (child != null) {
                layout(child);
                child = child.next;
            }

            if (node.child != null) {
                attachParent(node, join(node));
            } else {
                layoutLeaf(node);
            }
        }
    }

    protected mxRectangle horizontalLayout(TreeNode node, double x0, double y0, mxRectangle bounds) {
        node.x += x0 + node.offsetX;
        node.y += y0 + node.offsetY;
        bounds = apply(node, bounds);
        TreeNode child = node.child;

        if (child != null) {
            bounds = horizontalLayout(child, node.x, node.y, bounds);
            double siblingOffset = node.y + child.offsetY;
            TreeNode s = child.next;

            while (s != null) {
                bounds = horizontalLayout(s, node.x + child.offsetX, siblingOffset, bounds);
                siblingOffset += s.offsetY;
                s = s.next;
            }
        }

        return bounds;
    }

    protected mxRectangle verticalLayout(TreeNode node, Object parent, double x0, double y0, mxRectangle bounds) {
        node.x += x0 + node.offsetY;
        node.y += y0 + node.offsetX;
        bounds = apply(node, bounds);
        TreeNode child = node.child;

        if (child != null) {
            bounds = verticalLayout(child, node, node.x, node.y, bounds);
            double siblingOffset = node.x + child.offsetY;
            TreeNode s = child.next;

            while (s != null) {
                bounds = verticalLayout(s, node, siblingOffset, node.y + child.offsetX, bounds);
                siblingOffset += s.offsetY;
                s = s.next;
            }
        }

        return bounds;
    }

    /**
     * 
     */
    protected void attachParent(TreeNode node, double height) {
        double x = nodeDistance + levelDistance;
        double y2 = (height - node.width) / 2 - nodeDistance;
        double y1 = y2 + node.width + 2 * nodeDistance - height;

        node.child.offsetX = x + node.height;
        if (isBoundaryEvent(node.cell)) {
            node.child.offsetY = y1 + node.child.width;
        } else {
            node.child.offsetY = y1;
        }

        node.contour.upperHead = createLine(node.height, 0, createLine(x, y1, node.contour.upperHead));
        node.contour.lowerHead = createLine(node.height, 0, createLine(x, y2, node.contour.lowerHead));
    }

    /**
     * 
     */
    protected void layoutLeaf(TreeNode node) {
        double dist = 2 * nodeDistance;

        node.contour.upperTail = createLine(node.height + dist, 0, null);
        node.contour.upperHead = node.contour.upperTail;
        node.contour.lowerTail = createLine(0, -node.width - dist, null);
        node.contour.lowerHead = createLine(node.height + dist, 0, node.contour.lowerTail);
    }

    /**
     * 
     */
    protected double join(TreeNode node) {
        double dist = 2 * nodeDistance;

        TreeNode child = node.child;
        node.contour = child.contour;
        double h = child.width + dist;
        double sum = h;
        child = child.next;

        while (child != null) {
            double d = merge(node.contour, child.contour);
            child.offsetY = d + h;
            child.offsetX = 0;
            h = child.width + dist;
            sum += d + h;
            child = child.next;
        }

        return sum;
    }

    /**
     * 
     */
    protected double merge(Polygon p1, Polygon p2) {
        double x = 0;
        double y = 0;
        double total = 0;

        Polyline upper = p1.lowerHead;
        Polyline lower = p2.upperHead;

        while (lower != null && upper != null) {
            double d = offset(x, y, lower.dx, lower.dy, upper.dx, upper.dy);
            y += d;
            total += d;

            if (x + lower.dx <= upper.dx) {
                x += lower.dx;
                y += lower.dy;
                lower = lower.next;
            } else {
                x -= upper.dx;
                y -= upper.dy;
                upper = upper.next;
            }
        }

        if (lower != null) {
            Polyline b = bridge(p1.upperTail, 0, 0, lower, x, y);
            p1.upperTail = (b.next != null) ? p2.upperTail : b;
            p1.lowerTail = p2.lowerTail;
        } else {
            Polyline b = bridge(p2.lowerTail, x, y, upper, 0, 0);

            if (b.next == null) {
                p1.lowerTail = b;
            }
        }

        p1.lowerHead = p2.lowerHead;

        return total;
    }

    /**
     * 
     */
    protected double offset(double p1, double p2, double a1, double a2, double b1, double b2) {
        double d = 0;

        if (b1 <= p1 || p1 + a1 <= 0) {
            return 0;
        }

        double t = b1 * a2 - a1 * b2;

        if (t > 0) {
            if (p1 < 0) {
                double s = p1 * a2;
                d = s / a1 - p2;
            } else if (p1 > 0) {
                double s = p1 * b2;
                d = s / b1 - p2;
            } else {
                d = -p2;
            }
        } else if (b1 < p1 + a1) {
            double s = (b1 - p1) * a2;
            d = b2 - (p2 + s / a1);
        } else if (b1 > p1 + a1) {
            double s = (a1 + p1) * b2;
            d = s / b1 - (p2 + a2);
        } else {
            d = b2 - (p2 + a2);
        }

        if (d > 0) {
            return d;
        }

        return 0;
    }

    /**
     * 
     */
    protected Polyline bridge(Polyline line1, double x1, double y1, Polyline line2, double x2, double y2) {
        double dx = x2 + line2.dx - x1;
        double dy = 0;
        double s = 0;

        if (line2.dx == 0) {
            dy = line2.dy;
        } else {
            s = dx * line2.dy;
            dy = s / line2.dx;
        }

        Polyline r = createLine(dx, dy, line2.next);
        line1.next = createLine(0, y2 + line2.dy - dy - y1, r);

        return r;
    }

    /**
     * 
     */
    protected TreeNode createNode(Object cell) {
        TreeNode node = new TreeNode(cell);

        mxRectangle geo = getVertexBounds(cell);

        if (geo != null) {
            if (horizontal) {
                node.width = geo.getHeight();
                node.height = geo.getWidth();
            } else {
                node.width = geo.getWidth();
                node.height = geo.getHeight();
            }
        }

        return node;
    }

    /**
     * 
     */
    protected mxRectangle apply(TreeNode node, mxRectangle bounds) {
        mxRectangle g = graph.getModel().getGeometry(node.cell);

        if (node.cell != null && g != null) {
            if (isVertexMovable(node.cell)) {
                g = setVertexLocation(node.cell, node.x, node.y);
            }

            if (bounds == null) {
                bounds = new mxRectangle(g.getX(), g.getY(), g.getWidth(), g.getHeight());
            } else {
                bounds = new mxRectangle(Math.min(bounds.getX(), g.getX()), Math.min(bounds.getY(), g.getY()), Math.max(bounds.getX() + bounds.getWidth(), g.getX() + g.getWidth()), Math.max(bounds.getY()
                        + bounds.getHeight(), g.getY() + g.getHeight()));
            }
        }

        return bounds;
    }

    /**
     * 
     */
    protected Polyline createLine(double dx, double dy, Polyline next) {
        return new Polyline(dx, dy, next);
    }

    /**
     * 
     */
    protected static class TreeNode {
        /**
        	 * 
        	 */
        protected Object cell;

        /**
        	 * 
        	 */
        protected double x;
        protected double y;
        protected double width;
        protected double height;
        protected double offsetX;
        protected double offsetY;

        /**
        	 * 
        	 */
        protected TreeNode child;
        protected TreeNode next; // parent, sibling

        /**
        	 * 
        	 */
        protected Polygon contour = new Polygon();

        /**
        	 * 
        	 */
        public TreeNode(Object cell) {
            this.cell = cell;
        }

    }

    /**
     * 
     */
    protected static class Polygon {

        /**
        	 * 
        	 */
        protected Polyline lowerHead;
        protected Polyline lowerTail;
        protected Polyline upperHead;
        protected Polyline upperTail;

    }

    /**
     * 
     */
    protected static class Polyline {

        /**
        	 * 
        	 */
        protected double dx;
        protected double dy;

        /**
        	 * 
        	 */
        protected Polyline next;

        /**
        	 * 
        	 */
        protected Polyline(double dx, double dy, Polyline next) {
            this.dx = dx;
            this.dy = dy;
            this.next = next;
        }

    }

}
